#include<stdio.h>
void GetNextVal(int* nextval, char *str)
{
	int len = strlen(str);
	int k = -1;
	int i = 0;
	nextval[0] = -1;
	while (i < len - 1)
	{
		if (k == -1 || str[i] == str[k])
		{
			i++;
			k++;
			if (str[i] == str[k])
				nextval[i] = nextval[k];
			else
				nextval[i] = k;
		}
		else
			k = nextval[k];
	}
}

int strStr(char* hayStack, char* needle)
{
	int len_h = strlen(hayStack);
	int len_n = strlen(needle);
	int i = 0, j = 0;
	int *NextVal = (int*)malloc(sizeof(int) * len_n);
	GetNextVal(NextVal, needle);
	while (i < len_h && j < len_n)
	{
		if (hayStack[i] == needle[j])
		{
			i++;
			j++;
		}
		else if (j != 0)
		{
			j = NextVal[j];
			if (j == -1)
				j = 0;
		}
		else
			i++;
	}
	if (j >= len_n)
		return i - j;
	else
		return -1;
}